package com.cango.student.algorithm.sort;

public class HeapSort {

    /**
     * 建设堆
     * 数组中下标为i的左节点，就是i*2，右节点就是i*2+1，父节点i/2
     *
     * @param a
     * @param n
     */
    private static void buildHeap(int[] a, int n) {
        // i=n/2代表第一个非叶子节点。依次向上
        for (int i = n / 2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }

    /**
     * 自上往下堆化
     *
     * @param a 数组
     * @param n 总大小
     * @param i 开始节点
     */
    public static void heapify(int[] a, int n, int i) {
        // 循环找自己的左右节点
        while (true) {
            int maxPos = i;
            // 与左右节点比较，找出最大的，和自己调换位置
            if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
            // 最大值是自己则跳出
            if (maxPos == i) break;
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    /**
     * 排序
     * n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
     *
     * @param a
     * @param n
     */
    public static void sort(int[] a, int n) {
        // 建堆
        buildHeap(a, n);
        int k = n;
        while (k > 1) {
            // 1和最后值调换
            swap(a, 1, k);
            --k;
            // 堆化，始终把最大的值放入堆顶，从第一个进行堆化,自上而下
            heapify(a, k, 1);
        }
    }

    public static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public static void main(String[] args) {
        int[] s = {0, 7, 5, 19, 8, 4, 1, 20, 13, 16};
        sort(s, 9);

        for (int t : s) {
            System.out.println(t);
        }

        int[] b = new int[10];
        for (int t : b) {
            System.out.println(t);
        }
    }
}
